#![allow(dead_code, mutable_transmutes, non_camel_case_types, non_snake_case, non_upper_case_globals, unused_assignments, unused_mut)]
use std::mem;
use crate::alloc_testing::*;
extern "C" {
        }
pub type size_t = libc::c_ulong;
#[derive(Copy, Clone)]
#[repr(C)]
pub struct _AVLTree {
    pub root_node: *mut AVLTreeNode,
    pub compare_func: AVLTreeCompareFunc,
    pub num_nodes: libc::c_uint,
}
pub type AVLTreeCompareFunc = Option::<
    unsafe extern "C" fn(AVLTreeValue, AVLTreeValue) -> libc::c_int,
>;
pub type AVLTreeValue = *mut libc::c_void;
pub type AVLTreeNode = _AVLTreeNode;
#[derive(Copy, Clone)]
#[repr(C)]
pub struct _AVLTreeNode {
    pub children: [*mut AVLTreeNode; 2],
    pub parent: *mut AVLTreeNode,
    pub key: AVLTreeKey,
    pub value: AVLTreeValue,
    pub height: libc::c_int,
}
pub type AVLTreeKey = *mut libc::c_void;
pub type AVLTree = _AVLTree;
pub type AVLTreeNodeSide = libc::c_uint;
pub const AVL_TREE_NODE_RIGHT: AVLTreeNodeSide = 1;
pub const AVL_TREE_NODE_LEFT: AVLTreeNodeSide = 0;
#[no_mangle]
pub extern "C" fn avl_tree_new(
    mut compare_func: AVLTreeCompareFunc,
) -> *mut AVLTree {
    let new_tree: *mut AVLTree = unsafe {
        alloc_test_malloc(std::mem::size_of::<AVLTree>() as libc::c_ulong) as *mut AVLTree
    };

    if new_tree.is_null() {
        return std::ptr::null_mut();
    }

    let mut boxed_tree = unsafe { Box::from_raw(new_tree) };
    boxed_tree.root_node = std::ptr::null_mut();
    boxed_tree.compare_func = compare_func;
    boxed_tree.num_nodes = 0;
    let new_tree = Box::into_raw(boxed_tree);

    new_tree
}
extern "C" fn avl_tree_free_subtree(
    mut tree: *mut AVLTree,
    mut node: *mut AVLTreeNode,
) {
    if node.is_null() {
        return;
    }

    let boxed_node = unsafe { Box::from_raw(node) };
    avl_tree_free_subtree(
        tree,
        boxed_node.children[AVL_TREE_NODE_LEFT as libc::c_int as usize],
    );
    avl_tree_free_subtree(
        tree,
        boxed_node.children[AVL_TREE_NODE_RIGHT as libc::c_int as usize],
    );
    alloc_test_free(node as *mut libc::c_void);
    let node = Box::into_raw(boxed_node);
}
#[no_mangle]
pub extern "C" fn avl_tree_free(mut tree: *mut AVLTree) {
    if !tree.is_null() {
        let boxed_tree = unsafe { Box::from_raw(tree) };
        avl_tree_free_subtree(tree, boxed_tree.root_node);
        alloc_test_free(tree as *mut libc::c_void);
        let tree = Box::into_raw(boxed_tree);
    }
}
#[no_mangle]
pub extern "C" fn avl_tree_subtree_height(mut node: *mut AVLTreeNode) -> libc::c_int {
    if node.is_null() {
        return 0;
    } else {
        let boxed_node = unsafe { Box::from_raw(node) };
        let height = boxed_node.height;
        let node = Box::into_raw(boxed_node);
        return height;
    }
}
extern "C" fn avl_tree_update_height(mut node: *mut AVLTreeNode) {
    let mut left_subtree: *mut AVLTreeNode = std::ptr::null_mut();
    let mut right_subtree: *mut AVLTreeNode = std::ptr::null_mut();
    let mut left_height: libc::c_int = 0;
    let mut right_height: libc::c_int = 0;

    unsafe {
        left_subtree = (*node).children[AVL_TREE_NODE_LEFT as usize];
        right_subtree = (*node).children[AVL_TREE_NODE_RIGHT as usize];
    }

    left_height = avl_tree_subtree_height(left_subtree);
    right_height = avl_tree_subtree_height(right_subtree);

    let mut boxed_node = unsafe { Box::from_raw(node) };
    if left_height > right_height {
        boxed_node.height = left_height + 1;
    } else {
        boxed_node.height = right_height + 1;
    }
    let node = Box::into_raw(boxed_node);
}
extern "C" fn avl_tree_node_parent_side(mut node: *mut AVLTreeNode) -> AVLTreeNodeSide {
    let boxed_node = unsafe { Box::from_raw(node) };
    let parent = unsafe { Box::from_raw((*boxed_node).parent) };
    let side = if parent.children[AVL_TREE_NODE_LEFT as libc::c_int as usize] == node {
        AVL_TREE_NODE_LEFT
    } else {
        AVL_TREE_NODE_RIGHT
    };
    let node = Box::into_raw(boxed_node);
    let parent = Box::into_raw(parent);
    side
}
extern "C" fn avl_tree_node_replace(
    mut tree: *mut AVLTree,
    mut node1: *mut AVLTreeNode,
    mut node2: *mut AVLTreeNode,
) {
    let mut side: libc::c_int = 0;

    if !node2.is_null() {
        let mut boxed_node2 = unsafe { Box::from_raw(node2) };
        boxed_node2.parent = unsafe { (*node1).parent };
        node2 = Box::into_raw(boxed_node2);
    }

    let mut boxed_tree = unsafe { Box::from_raw(tree) };
    if unsafe { (*node1).parent.is_null() } {
        boxed_tree.root_node = node2;
    } else {
        side = avl_tree_node_parent_side(node1) as libc::c_int;
        let mut boxed_parent = unsafe { Box::from_raw(unsafe { (*node1).parent }) };
        boxed_parent.children[side as usize] = node2;
        unsafe { avl_tree_update_height((*node1).parent) };
        unsafe { (*node1).parent = Box::into_raw(boxed_parent) };
    }
    tree = Box::into_raw(boxed_tree);
}
extern "C" fn avl_tree_rotate(
    mut tree: *mut AVLTree,
    mut node: *mut AVLTreeNode,
    mut direction: AVLTreeNodeSide,
) -> *mut AVLTreeNode {
    let mut new_root: *mut AVLTreeNode = std::ptr::null_mut();

    unsafe {
        new_root = (*node)
            .children[(1 as libc::c_int as libc::c_uint)
            .wrapping_sub(direction as libc::c_uint) as usize];
    }

    avl_tree_node_replace(tree, node, new_root);

    let mut boxed_node = unsafe { Box::from_raw(node) };
    let mut boxed_new_root = unsafe { Box::from_raw(new_root) };

    boxed_node
        .children[(1 as libc::c_int as libc::c_uint)
        .wrapping_sub(direction as libc::c_uint) as usize] = boxed_new_root.children[direction as usize];
    boxed_new_root.children[direction as usize] = node;
    boxed_node.parent = new_root;

    if !boxed_node
        .children[(1 as libc::c_int as libc::c_uint)
        .wrapping_sub(direction as libc::c_uint) as usize]
        .is_null()
    {
        unsafe {
            (*boxed_node
                .children[(1 as libc::c_int as libc::c_uint)
                .wrapping_sub(direction as libc::c_uint) as usize])
                .parent = node;
        }
    }

    node = Box::into_raw(boxed_node);
    new_root = Box::into_raw(boxed_new_root);

    avl_tree_update_height(new_root);
    avl_tree_update_height(node);

    new_root
}
extern "C" fn avl_tree_node_balance(
    mut tree: *mut AVLTree,
    mut node: *mut AVLTreeNode,
) -> *mut AVLTreeNode {
    let mut left_subtree: *mut AVLTreeNode = std::ptr::null_mut();
    let mut right_subtree: *mut AVLTreeNode = std::ptr::null_mut();
    let mut child: *mut AVLTreeNode = std::ptr::null_mut();
    let mut diff: libc::c_int = 0;

    let boxed_node = unsafe { Box::from_raw(node) };
    left_subtree = boxed_node.children[AVL_TREE_NODE_LEFT as libc::c_int as usize];
    right_subtree = boxed_node.children[AVL_TREE_NODE_RIGHT as libc::c_int as usize];
    node = Box::into_raw(boxed_node);

    diff = avl_tree_subtree_height(right_subtree)
        - avl_tree_subtree_height(left_subtree);

    if diff >= 2 {
        child = right_subtree;
        if avl_tree_subtree_height(
            unsafe { (*child).children[AVL_TREE_NODE_RIGHT as libc::c_int as usize] },
        )
            < avl_tree_subtree_height(
                unsafe { (*child).children[AVL_TREE_NODE_LEFT as libc::c_int as usize] },
            )
        {
            avl_tree_rotate(tree, right_subtree, AVL_TREE_NODE_RIGHT);
        }
        node = avl_tree_rotate(tree, node, AVL_TREE_NODE_LEFT);
    } else if diff <= -2 {
        child = unsafe { (*node).children[AVL_TREE_NODE_LEFT as libc::c_int as usize] };
        if avl_tree_subtree_height(
            unsafe { (*child).children[AVL_TREE_NODE_LEFT as libc::c_int as usize] },
        )
            < avl_tree_subtree_height(
                unsafe { (*child).children[AVL_TREE_NODE_RIGHT as libc::c_int as usize] },
            )
        {
            avl_tree_rotate(tree, left_subtree, AVL_TREE_NODE_LEFT);
        }
        node = avl_tree_rotate(tree, node, AVL_TREE_NODE_RIGHT);
    }

    avl_tree_update_height(node);
    node
}
extern "C" fn avl_tree_balance_to_root(
    mut tree: *mut AVLTree,
    mut node: *mut AVLTreeNode,
) {
    let mut rover: *mut AVLTreeNode = node;
    while !rover.is_null() {
        
        unsafe {
            rover = avl_tree_node_balance(tree, rover);
            rover = (*rover).parent;
        }
    }
}
#[no_mangle]
pub extern "C" fn avl_tree_insert(
    mut tree: *mut AVLTree,
    mut key: AVLTreeKey,
    mut value: AVLTreeValue,
) -> *mut AVLTreeNode {
    let mut rover: *mut *mut AVLTreeNode = std::ptr::null_mut();
    let mut new_node: *mut AVLTreeNode = std::ptr::null_mut();
    let mut previous_node: *mut AVLTreeNode = std::ptr::null_mut();

    
    unsafe {
        rover = &mut (*tree).root_node;
        previous_node = std::ptr::null_mut();

        while !(*rover).is_null() {
            previous_node = *rover;
            if ((*tree).compare_func).expect("non-null function pointer")(key, (**rover).key) < 0 {
                rover = &mut *((**rover).children)
                    .as_mut_ptr()
                    .offset(AVL_TREE_NODE_LEFT as isize)
                    as *mut *mut AVLTreeNode;
            } else {
                rover = &mut *((**rover).children)
                    .as_mut_ptr()
                    .offset(AVL_TREE_NODE_RIGHT as isize)
                    as *mut *mut AVLTreeNode;
            }
        }

        new_node = alloc_test_malloc(std::mem::size_of::<AVLTreeNode>() as libc::c_ulong)
            as *mut AVLTreeNode;

        if new_node.is_null() {
            return std::ptr::null_mut();
        }

        (*new_node).children[AVL_TREE_NODE_LEFT as usize] = std::ptr::null_mut();
        (*new_node).children[AVL_TREE_NODE_RIGHT as usize] = std::ptr::null_mut();
        (*new_node).parent = previous_node;
        (*new_node).key = key;
        (*new_node).value = value;
        (*new_node).height = 1;
        *rover = new_node;
        avl_tree_balance_to_root(tree, previous_node);
        (*tree).num_nodes = (*tree).num_nodes.wrapping_add(1);
    }

    new_node
}
extern "C" fn avl_tree_node_get_replacement(
    mut tree: *mut AVLTree,
    mut node: *mut AVLTreeNode,
) -> *mut AVLTreeNode {
    let mut left_subtree: *mut AVLTreeNode = std::ptr::null_mut();
    let mut right_subtree: *mut AVLTreeNode = std::ptr::null_mut();
    let mut result: *mut AVLTreeNode = std::ptr::null_mut();
    let mut child: *mut AVLTreeNode = std::ptr::null_mut();
    let mut left_height: libc::c_int = 0;
    let mut right_height: libc::c_int = 0;
    let mut side: libc::c_int = 0;

    let boxed_node = unsafe { Box::from_raw(node) };
    left_subtree = boxed_node.children[AVL_TREE_NODE_LEFT as libc::c_int as usize];
    right_subtree = boxed_node.children[AVL_TREE_NODE_RIGHT as libc::c_int as usize];
    node = Box::into_raw(boxed_node);

    if left_subtree.is_null() && right_subtree.is_null() {
        return std::ptr::null_mut();
    }

    left_height = avl_tree_subtree_height(left_subtree);
    right_height = avl_tree_subtree_height(right_subtree);

    if left_height < right_height {
        side = AVL_TREE_NODE_RIGHT as libc::c_int;
    } else {
        side = AVL_TREE_NODE_LEFT as libc::c_int;
    }

    let boxed_node = unsafe { Box::from_raw(node) };
    result = boxed_node.children[side as usize];
    node = Box::into_raw(boxed_node);

    while !unsafe { (*result).children[(1 as libc::c_int - side) as usize] }.is_null() {
        let boxed_result = unsafe { Box::from_raw(result) };
        result = boxed_result.children[(1 as libc::c_int - side) as usize];
        let result_ptr = Box::into_raw(boxed_result);
    }

    let boxed_result = unsafe { Box::from_raw(result) };
    child = boxed_result.children[side as usize];
    result = Box::into_raw(boxed_result);

    avl_tree_node_replace(tree, result, child);
    avl_tree_update_height(unsafe { (*result).parent });

    result
}
#[no_mangle]
pub extern "C" fn avl_tree_remove_node(
    mut tree: *mut AVLTree,
    mut node: *mut AVLTreeNode,
) {
    let mut swap_node: *mut AVLTreeNode = std::ptr::null_mut();
    let mut balance_startpoint: *mut AVLTreeNode = std::ptr::null_mut();
    let mut i: libc::c_int = 0;

    swap_node = avl_tree_node_get_replacement(tree, node);

    if swap_node.is_null() {
        avl_tree_node_replace(tree, node, std::ptr::null_mut());
        balance_startpoint = unsafe { (*node).parent };
    } else {
        if unsafe { (*swap_node).parent == node } {
            balance_startpoint = swap_node;
        } else {
            balance_startpoint = unsafe { (*swap_node).parent };
        }
        i = 0;
        while i < 2 {
            unsafe {
                (*swap_node).children[i as usize] = (*node).children[i as usize];
                if !(*swap_node).children[i as usize].is_null() {
                    (*(*swap_node).children[i as usize]).parent = swap_node;
                }
            }
            i += 1;
        }
        unsafe {
            (*swap_node).height = (*node).height;
            avl_tree_node_replace(tree, node, swap_node);
        }
    }

    unsafe {
        alloc_test_free(node as *mut libc::c_void);
        (*tree).num_nodes = (*tree).num_nodes.wrapping_sub(1);
        avl_tree_balance_to_root(tree, balance_startpoint);
    }
}
#[no_mangle]
pub extern "C" fn avl_tree_lookup_node(
    mut tree: *mut AVLTree,
    mut key: AVLTreeKey,
) -> *mut AVLTreeNode {
    let mut node: *mut AVLTreeNode = std::ptr::null_mut();
    let mut diff: libc::c_int = 0;

    
    unsafe {
        node = (*tree).root_node;
    }

    while !node.is_null() {
        
        unsafe {
            diff = ((*tree).compare_func)
                .expect("non-null function pointer")(key, (*node).key);
        }

        if diff == 0 {
            return node;
        } else if diff < 0 {
            
            unsafe {
                node = (*node).children[AVL_TREE_NODE_LEFT as usize];
            }
        } else {
            
            unsafe {
                node = (*node).children[AVL_TREE_NODE_RIGHT as usize];
            }
        }
    }

    return std::ptr::null_mut();
}
#[no_mangle]
pub extern "C" fn avl_tree_remove(
    mut tree: *mut AVLTree,
    mut key: AVLTreeKey,
) -> libc::c_int {
    let mut node: *mut AVLTreeNode = std::ptr::null_mut();

    node = avl_tree_lookup_node(tree, key);

    if node.is_null() {
        return 0;
    }

    avl_tree_remove_node(tree, node);

    return 1;
}
#[no_mangle]
pub extern "C" fn avl_tree_lookup(
    mut tree: *mut AVLTree,
    mut key: AVLTreeKey,
) -> AVLTreeValue {
    let mut node: *mut AVLTreeNode = std::ptr::null_mut();

    node = avl_tree_lookup_node(tree, key);

    if node.is_null() {
        return 0 as *mut libc::c_void;
    } else {
        let boxed_node = unsafe { Box::from_raw(node) };
        let value = boxed_node.value;
        let node = Box::into_raw(boxed_node);
        return value;
    }
}
#[no_mangle]
pub extern "C" fn avl_tree_root_node(mut tree: *mut AVLTree) -> *mut AVLTreeNode {
    let boxed_tree = unsafe { Box::from_raw(tree) };
    let root_node = boxed_tree.root_node;
    let tree = Box::into_raw(boxed_tree);
    root_node
}
#[no_mangle]
pub extern "C" fn avl_tree_node_key(mut node: *mut AVLTreeNode) -> AVLTreeKey {
    let boxed_node = unsafe { Box::from_raw(node) };
    let key = boxed_node.key;
    let node = Box::into_raw(boxed_node);
    key
}
#[no_mangle]
pub extern "C" fn avl_tree_node_value(mut node: *mut AVLTreeNode) -> AVLTreeValue {
    let boxed_node = unsafe { Box::from_raw(node) };
    let value = boxed_node.value;
    let node = Box::into_raw(boxed_node);
    value
}
#[no_mangle]
pub extern "C" fn avl_tree_node_child(
    mut node: *mut AVLTreeNode,
    mut side: AVLTreeNodeSide,
) -> *mut AVLTreeNode {
    if side as libc::c_uint == AVL_TREE_NODE_LEFT as libc::c_int as libc::c_uint
        || side as libc::c_uint == AVL_TREE_NODE_RIGHT as libc::c_int as libc::c_uint
    {
        let boxed_node = unsafe { Box::from_raw(node) };
        let child = boxed_node.children[side as usize];
        node = Box::into_raw(boxed_node);
        return child;
    } else {
        return std::ptr::null_mut();
    }
}
#[no_mangle]
pub extern "C" fn avl_tree_node_parent(mut node: *mut AVLTreeNode) -> *mut AVLTreeNode {
    let boxed_node = unsafe { Box::from_raw(node) };
    let parent = boxed_node.parent;
    let node = Box::into_raw(boxed_node);
    parent
}
#[no_mangle]
pub extern "C" fn avl_tree_num_entries(tree: *mut AVLTree) -> libc::c_uint {
    let boxed_tree = unsafe { Box::from_raw(tree) };
    let num_nodes = boxed_tree.num_nodes;
    let tree = Box::into_raw(boxed_tree);
    num_nodes
}
extern "C" fn avl_tree_to_array_add_subtree(
    mut subtree: *mut AVLTreeNode,
    mut array: *mut AVLTreeValue,
    mut index: *mut libc::c_int,
) {
    if subtree.is_null() {
        return;
    }

    
    unsafe {
        avl_tree_to_array_add_subtree(
            (*subtree).children[AVL_TREE_NODE_LEFT as libc::c_int as usize],
            array,
            index,
        );

        let ref mut fresh0 = *array.offset(*index as isize);
        *fresh0 = (*subtree).key;
        *index += 1;

        avl_tree_to_array_add_subtree(
            (*subtree).children[AVL_TREE_NODE_RIGHT as libc::c_int as usize],
            array,
            index,
        );
    }
}
#[no_mangle]
pub extern "C" fn avl_tree_to_array(mut tree: *mut AVLTree) -> *mut AVLTreeValue {
    let mut array: *mut AVLTreeValue = std::ptr::null_mut();
    let mut index: libc::c_int = 0;

    let boxed_tree = unsafe { Box::from_raw(tree) };
    array = alloc_test_malloc(
        (std::mem::size_of::<AVLTreeValue>() as libc::c_ulong)
            .wrapping_mul(boxed_tree.num_nodes as libc::c_ulong),
    ) as *mut AVLTreeValue;
    tree = Box::into_raw(boxed_tree);

    if array.is_null() {
        return std::ptr::null_mut();
    }

    let boxed_tree = unsafe { Box::from_raw(tree) };
    avl_tree_to_array_add_subtree(boxed_tree.root_node, array, &mut index);
    tree = Box::into_raw(boxed_tree);

    array
}
